package first.niuke.simple;

/**
 * @ClassName NC74
 * @description:
 * @author: 荣燊
 * @create: 2021-06-13 20:09
 **/
public class NC74 {
    // 数组在升序数组中出现的次数
    public static void main(String[] args) {

    }

    /**
     * 因为是升序数组，所以用二分，减少时间复杂度
     */
    public static int GetNumberOfK(int[] array ,int k) {
        if (array == null || array.length == 0) {
            return 0;
        }

        int right = array.length - 1;
        int left = 0;

        int middle = 0;
        while (left < right) {
            middle = (left + right) / 2;
            if (array[middle] > k) {
                right = middle - 1;
            } else if (array[middle] < k) {
                left = middle + 1;
            } else {
                break;
            }
        }

        int count = 0;
        for (int i=left; i<=right; i++) {
            if (array[i] == k) {
                count++;
            }
        }
        return count;
    }

    public static int GetNumberOfTime(int[] array , int i, int j, int k) {
        return 0;
    }
}
